% Find which edge to add hurts the graph the most
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function [bestx,besty] = hurtGraph(G,varargin);
%
%   This function cycles through all possible edges to remove from the
%   graph to see which one hurts most.
%
%   INPUTS:     G - adjacency matrix for graph G
%
%   OUTPUTS:    bestx - one vertex for best edge to remove from G
%               besty - one vertex for best edge to remove from G
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [bestx,besty,maxEccentricity] = hurtGraph(G,varargin);

% Get sizes & initialize some values
[xmax ymax] = size(G);
bestx = 0;
besty = 0;
% Get initial values
distances = GetDistances(G);
[eccentricities, graphDiameter, graphRadius, ... 
    graphCenters, graphExtremes] = GetEccentricities(distances);
avgEccentricity = sum(eccentricities)/xmax;
maxEccentricity = avgEccentricity
s = sum(G);

for x = 1:xmax
    for y = 1:ymax
        % remove an edge if it exists
        if (G(x,y) == 1),
            %[x y]
            %if (sum(G(x)) > 1 && sum(G(y)) > 1),
            if (s(x) > 1 && s(y) > 1),
                Gtest = removeEdge(x,y,G);
%                 s = sum(Gtest);
%                 for z = 1:xmax
%                     if (s(z) == 0),
%                         continue;
%                     end;
%                 end;
                distances = GetDistances(Gtest);
                [eccentricities, graphDiameter, graphRadius, ...
                    graphCenters, graphExtremes] = GetEccentricities(distances);
                avgEccentricity = sum(eccentricities)/xmax;
                % if removed edge makes a new record high eccentricity, record
                % it as our best
                if (avgEccentricity > maxEccentricity),
                    %sprintf('Found new max')
                    maxEccentricity = avgEccentricity;
                    bestx = x;
                    besty = y;
                end;
            end;
        end;
    end;
end;